МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НУ”ЛЬВІВСЬКА ПОЛІТЕХНІКА”
КАФЕДРА АВТОМАТИКИ І ТЕЛЕМЕХАНІКИ
ЗВІТ
про виконання лабораторної роботи№3
з дисципліни „Алгоритмічні основи криптології”
на тему:
“Метод Ньютона для розв’язування
систем нелінійних рівнянь ”
Мета роботи: ознайомитися з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона.
Завдання: написати програму на мові програмування Сі яка б розв’язувала систему нелінійних рівнянь модифікованим методом Ньютона, реалізувати обертання матриць методом Гауса, а обчислення похідних методом кінцевих різниць.
Система рівнянь:
x[1]-x[1]*x[1]+0.8*x[2]*x[2]+0.1=0
x[2]-2*x[1]*x[2]-0.1=0
Початкові наближення: x[1]=0; x[2]=0;
Блок-схема алгоритму.
Повний текст програми.
#include<stdio.h>
#include<math.h>
#define n 2
#define e 0.000001
#define h 10e-9
static float Jc[n+2][n+2],Jcob[n+2][n+2];
Gaus(float a[n+2][n+2])
{int i,k,p,f; float v[n+2][n+2]; float s=0; float b[n+1];
for (f=1;f<=n;f++)
{for (i=1;i<=n;i++)
{if (f==i)
b[i]=1; else b[i]=0;
a[i][n+1]=((-1)*b[i]); }
for (p=1;p<=(n-1);p++)
for (i=p+1;i<=n;i++)
for (k=p+1;k<=(n+1);k++)
{v[p][k]=((-1)*a[p][k]/a[p][p]);
a[i][k]=(a[i][p]*v[p][k])+a[i][k];}
Jcob[n][f]=(-1)*a[n][n+1]/a[n][n];
for (i=n-1;i>=1;i--)
{for (k=i+1;k<=n;k++)
s+=v[i][k]*Jc[n][f];
Jcob[n-1][f]=v[i][n+1]+s;
s=0;}} return;}
float f(float x1,float x2,int i)
{ if (i==1)
return (x1-(x1*x1)+0.8*(x2*x2)+0.1);else
return (x2-(2*x1*x2)-0.1); }
main()
{ int i,j;
float x[n+2]; int m; float max;
float xp,yp,s1;
x[1]=0;x[2]=0;
do { xp=x[1]; yp=x[2];
/*Metod kincevyh riznyts*/
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
{if (j==1)
Jc[i][j]=(f(x[j]+h,x[j+1],i)-f(x[j],x[j+1],i))/h;
else Jc[i][j]=(f(x[1],x[j]+h,i)-f(x[1],x[j],i))/h; }
Gaus(Jc);
for (i=1;i<=n;i++)
{ s1=0;
for (j=1;j<=n;j++)
{ if (j==1)
Jcob[i][j]*=f(x[j],x[j+1],i);
else Jcob[i][j]*=f(x[j-1],x[j],i);
s1+=Jcob[i][j];}
if (i==1)
x[i]=xp-s1; else
x[i]=yp-s1; }
max=fabs((x[1]-xp)/x[1]);
іf (fabs((x[2]-yp)/x[2])>max)
max=fabs((x[2]-yp)/x[2]);
if (max<e)
{m=1;break;}
else m=0;
} while (m!=1);
for (i=1;i<=n;i++)
printf("\nx[%d]=%2.5f",i,x[i]);
printf("\n f1= %2.5f",f(x[1],x[2],1));
printf("\n f2= %2.5f",f(x[1],x[2],2)); }
Результати обчислень.
x[1]=-0.09634
x[2]=-0.08384
Перевірка:
f1= 0.00000
f2= 0.00000
Висновок:
Розв’язання систем нелінійних алгебраїчних рівнянь методом Ньютона можна досить легко реалізувати на ЕОМ за допомогою програми в середовищі Сі. Основна перевага модифікованого методу Ньютона полягає в тому, що при використанні цього методу якобіан замінюють правильно підібраною матрицею, яку зберігають сталою протягом деякого числа ітерацій, а потім на певній ітерації її заново обчислюють і присвоюють знайдене значення якобіану. Це дозволяє значно зекономити машинний час виконання програми. Розв’язання таких систем на ЕОМ є дуже актуальним, оскільки цей процес є набагато легшим та короткотривалішим ніж розв’язання систем нелінійних рівнянь вручну.
